package com.markus.code.动态规划;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/17 18:30
 * todo: 回文子串
 */
public class LeetCode_647 {
    /**
     * 这个题也可以用范围尝试模型来做，[L...R]是否是回文串
     * 我们来划分一下它的可能性
     * 因为题目说是回文子串，所以一定要要求连续的字符串
     * 只有一种可能：
     *      dp[L][R] = dp[L+1][R-1] && 【L】==【R】
     */
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0){
            return 0;
        }
        if (s.length() == 1){
            return 1;
        }
        if (s.length() == 2){
            return s.charAt(0) == s.charAt(1) ? 3:2;
        }
        char[] str = s.toCharArray();
        boolean [][]dp = new boolean[str.length][str.length];
        //记录在[L...R]上是回文串的数量
        //初始值的意义在于每个字符都是一个回文子串
        int res = str.length;
        //先填基本数据
        for (int i=0;i<dp.length;i++){
            dp[i][i] = true;
            if (i != dp.length-1){
                dp[i][i+1] = str[i] == str[i+1] ? true : false;
                res += dp[i][i+1]?1:0;
            }
        }
        //再填普遍数据
        for (int i=dp.length-3;i>=0;i--){
            for (int j=i+2;j<dp[i].length;j++){
                dp[i][j] = str[i]==str[j] && dp[i+1][j-1];
                res += dp[i][j]?1:0;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        LeetCode_647 demo = new LeetCode_647();
        String s = "aaa";
        System.out.println(demo.countSubstrings(s));
    }
}
